package 力扣算法练习.main1.part1;

import java.util.ArrayList;
import java.util.List;

public class day7 {
    public static class ListNode {
        int val;
        ListNode next;
        ListNode() {
        }
        ListNode(int val) {
            this.val = val;
        }
        ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }
    }

    /*
    给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。
    https://leetcode.cn/problems/remove-nth-node-from-end-of-list/
     */
    public ListNode removeNthFromEnd(ListNode head, int n) {
        //用双指针法,先一个指针先走n-1步然后两个一起走先走的到末尾了后走的就是要删除的位置
        if (head == null) return null;
        ListNode pre =head, next = head;
        ListNode parent = null;//记录要删除的前一个方便删除节点
        while (n > 1 && next.next != null) {
            next = next.next;
            n--;
        }
        while (next.next != null) {
            parent = pre;
            pre = pre.next;
            next = next.next;
        }
        //删除节点
        if (parent==null) {
            head = head.next;//要删除的是头节点
            return head;
        }
        parent.next = pre.next;
        return head;
    }


    /*
    数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。
    https://leetcode.cn/problems/generate-parentheses/
     */
    //来自官方解下面的点赞数最多的解
    List<String> res = new ArrayList<>();
    public List<String> generateParenthesis(int n) {
        if(n <= 0){
            return res;
        }
        getParenthesis("",n,n);
        return res;
    }

    private void getParenthesis(String str,int left, int right) {
        if(left == 0 && right == 0 ){
            res.add(str);
            return;
        }
        if(left == right){
            //剩余左右括号数相等，下一个只能用左括号
            getParenthesis(str+"(",left-1,right);
        }else if(left < right){
            //剩余左括号小于右括号，下一个可以用左括号也可以用右括号
            if(left > 0){
                getParenthesis(str+"(",left-1,right);
            }
            getParenthesis(str+")",left,right-1);
        }
    }
}
